	package br.uece.comp.paa.entity.ts;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import br.uece.comp.paa.entity.Aleatorio;
import br.uece.comp.paa.entity.GeradorArvoreMinima;
import br.uece.comp.paa.entity.Kruskal;
import br.uece.comp.paa.entity.grafo.Aresta;
import br.uece.comp.paa.entity.grafo.Grafo;
import br.uece.comp.paa.util.RelacaoEquivalencia;

public class BuscaTabu extends GeradorArvoreMinima {

	public final int LIMITE_ITERACOES;

	public static final float PERCENTUAL_TOLERANCIA = 1.02f;

	public static final int DURACAO_TABU_RETIRADA = 10;

	public static final int DURACAO_TABU_ADICIONADA = 9;

	public static final int REMOVER = 0;

	public static final int ADICIONAR = 1;

	private static final int GRUPO_A = 0;

	private static final int GRUPO_B = 1;

	private Grafo melhor;

	private Grafo temp;

	private double minimo;

	GeradorArvoreMinima gerador;

	public List<AtributoTabu> listaTabu;

	public List<Aresta> arestasMovimento;

	private final int QTD_VERTICES;

	public BuscaTabu(Grafo g) {
		super(g);
		gerador = new Kruskal(g);
		minimo = gerador.gerar().grafo.getCustoTotal();

		QTD_VERTICES = g.getVertices().length;
		LIMITE_ITERACOES = QTD_VERTICES * 100;
		listaTabu = new LinkedList<AtributoTabu>();
		arestasMovimento = new LinkedList<Aresta>();
	}

	@Override
	protected Grafo gerar(Grafo g, int grauMaximo, double custoMaximo) {
		temp = gerador.gerar(grauMaximo, 1, custoMaximo).get(0).grafo;
		melhor = temp;

		int iteracoes = 0;
		Aresta remover, adicionar;
		Grafo pivot;

		while (iteracoes < LIMITE_ITERACOES
				&& melhor.getCustoTotal() > minimo * PERCENTUAL_TOLERANCIA
				&& escolherArestas(grauMaximo)) {
			remover = arestasMovimento.get(REMOVER);
			adicionar = arestasMovimento.get(ADICIONAR);

			pivot = temp.substituirAresta(remover, adicionar);
			System.out.print("CUSTO ATUAL: " + melhor.getCustoTotal() + " = ");
			System.out.println("CUSTO PIVOT: " + pivot.getCustoTotal());

			if (pivot.getCustoTotal() < melhor.getCustoTotal()) {
				melhor = pivot;
			}

			atualizarListaTabu(remover, adicionar);

			if (iteracoes % QTD_VERTICES == 0) {
				temp = diversificar();
			}
			iteracoes++;

		}

		System.out.println("LIMITE INFERIOR: "
				+ (minimo * PERCENTUAL_TOLERANCIA));
		System.out.println("CUSTO ALCANÇADO: " + melhor.getCustoTotal());
		System.out.println("QTD ITERACOES: " + (iteracoes - 1));
		return melhor;
	}

	private Grafo diversificar() {

		while (listaTabu.size() > 0) {
			listaTabu.remove(0);
		}

		return new Aleatorio(getGrafo()).gerar().grafo;
	}

	private void atualizarListaTabu(Aresta remover, Aresta adicionar) {
		Iterator<AtributoTabu> iter = listaTabu.iterator();
		AtributoTabu at;

		while (iter.hasNext()) {
			at = iter.next();
			at.tempo--;
		}

		int qtd = listaTabu.size();

		for (int i = 0; i < qtd; i++) {
			at = listaTabu.get(i);
			if (at.tempo <= 0) {
				listaTabu.remove(i);
				i--;
				qtd--;
			}
		}

		listaTabu.add(new AtributoTabu(remover, DURACAO_TABU_RETIRADA));
		listaTabu.add(new AtributoTabu(adicionar, DURACAO_TABU_ADICIONADA));
	}

	private boolean escolherArestas(int grauMaximo) {

		// ESCOLHER ARESTA PARA REMOVER...
		// ESCOLHER A MAIOR ARESTA QUE NAO ESTEJA NA LISTA TABU.
		Double[][] matrizCustoAgm = melhor.getMatrizCusto();
		final int qtdVertices = melhor.getVertices().length;
		List<Aresta> removerPassadas = new LinkedList<Aresta>();
		int[] grupo = new int[qtdVertices];
		int[] grau = new int[qtdVertices];

		Aresta remover = null, adicionar = null;

		for (int k = 0; k < qtdVertices - 1; k++) {

			for (int i = 0; i < grupo.length; i++) {
				grupo[i] = GRUPO_A;
				melhor.atualizarGrau();
				grau[i] = melhor.getVertices()[i].getDegree();
			}

			// OBTER ARESTA REMOVER INICIAL

			for (int i = 0; i < qtdVertices; i++) {
				for (int j = i + 1; j < qtdVertices; j++) {
					if (matrizCustoAgm[i][j] != null && !ehTabuAtiva(i, j)) {
						remover = new Aresta(i, j, matrizCustoAgm[i][j]);
					}
				}
			}

			if (remover != null) {
				int v1, v2;
				v1 = remover.getVertice1();
				v2 = remover.getVertice2();

				for (int i = 0; i < qtdVertices; i++) {
					for (int j = i + 1; j < qtdVertices; j++) {
						if (matrizCustoAgm[i][j] != null
								&& matrizCustoAgm[i][j] > matrizCustoAgm[v1][v2]
								&& !ehTabuAtiva(i, j)
								&& !pertenceLista(i, j, removerPassadas)) {
							v1 = i;
							v2 = j;
						}
					}
				}

				remover = new Aresta(v1, v2, matrizCustoAgm[v1][v2]);
				System.out.println("Interação: k=" + k);
				System.out.println("Remover: " + remover);
				removerPassadas.add(remover);

				double d = matrizCustoAgm[v1][v2];
				matrizCustoAgm[v1][v2] = null;
				matrizCustoAgm[v2][v1] = null;
				marcarNovoGrupo(grupo, v2, matrizCustoAgm);
				matrizCustoAgm[v1][v2] = d;
				matrizCustoAgm[v2][v1] = d;

				grau[v1]--;
				grau[v2]--;

			} else {
				return false;
			}

			// ESCOLHER ARESTA PARA ADICIONAR.
			Double[][] matrizCustoGrafo = getGrafo().getMatrizCusto();
			// OBTER ARESTA ADICIONAR INICIAL
			for (int i = 0; i < qtdVertices; i++) {
				for (int j = i + 1; j < qtdVertices; j++) {
					if (matrizCustoGrafo[i][j] != null
							&& matrizCustoAgm[i][j] == null
							&& !ehTabuAtiva(i, j) && (grupo[i] != grupo[j])
							&& grau[i] < grauMaximo && grau[j] < grauMaximo) {
						adicionar = new Aresta(i, j, matrizCustoGrafo[i][j]);
					}
				}
			}

			System.out.println("Adicionar Inicial:" + adicionar);
			if (adicionar != null) {
				int v1, v2;
				v1 = adicionar.getVertice1();
				v2 = adicionar.getVertice2();

				for (int i = 0; i < qtdVertices; i++) {
					for (int j = i + 1; j < qtdVertices; j++) {
						if (matrizCustoGrafo[i][j] != null
								&& matrizCustoAgm[i][j] == null
								&& matrizCustoGrafo[i][j] < matrizCustoGrafo[v1][v2]
								&& !ehTabuAtiva(i, j) && (grupo[i] != grupo[j])
								&& grau[i] < grauMaximo && grau[j] < grauMaximo) {
							v1 = i;
							v2 = j;
						}
					}
				}

				adicionar = new Aresta(v1, v2, matrizCustoGrafo[v1][v2]);
				System.out.println("Remover: " + adicionar.getVertice1() + ", "
						+ adicionar.getVertice2());
				break;
			}
		}

		if (remover != null && adicionar != null) {
			arestasMovimento.add(REMOVER, remover);
			arestasMovimento.add(ADICIONAR, adicionar);

			return true;
		} else {
			return false;
		}
	}

	private void marcarNovoGrupo(int[] grupo, int v, Double[][] matrizCustoAgm) {
		if (grupo[v] != GRUPO_B) {
			grupo[v] = GRUPO_B;
			for (int i = 0; i < matrizCustoAgm[v].length; i++) {
				if (matrizCustoAgm[v][i] != null) {
					marcarNovoGrupo(grupo, i, matrizCustoAgm);
				}
			}
		}
	}

	private boolean ehTabuAtiva(int v1, int v2) {
		Iterator<AtributoTabu> iter = listaTabu.iterator();
		Aresta a = new Aresta(v1, v2, 0d);
		Aresta b;

		while (iter.hasNext()) {
			b = iter.next().aresta;
			if (RelacaoEquivalencia.ehArestaEquivalente(a, b)) {
				return true;
			}
		}
		return false;
	}

	private boolean pertenceLista(int v1, int v2, List<Aresta> lista) {
		Iterator<Aresta> iter = lista.iterator();
		Aresta a = new Aresta(v1, v2, 0d);
		Aresta b;

		while (iter.hasNext()) {
			b = iter.next();
			if (RelacaoEquivalencia.ehArestaEquivalente(a, b)) {
				return true;
			}
		}
		return false;
	}
}